//
// Created by Administrator on 2021/9/14.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    string findLongestWord(string s, vector<string> &dictionary) {
        // 先对字典排序 按照长度和字典序
        sort(dictionary.begin(), dictionary.end(), [](string &a, string &b) {
            return a.size() > b.size() or (a.size() == b.size() and a < b);
        });
        // 再遍历字典，只要有一个成功匹配，就可以结束了
        for (int i = 0; i < dictionary.size(); ++i) {
            if (dictionary[i].size() > s.size()) {
                continue;
            }
            int ptr = 0; // 指向当前单词的指针
            for (int j = 0; j < s.size(); ++j) {
                if (dictionary[i][ptr] == s[j]) {
                    ++ptr;
                }
                if (ptr == dictionary[i].size())
                    return dictionary[i];
            }
        }
        return "";
    }
};

class Solution2 { // dp
public:
    string findLongestWord(string s, vector<string> &dic) {
        sort(dic.begin(), dic.end(), [](string &&a, string &&b) {
            return a.size() > b.size() or a.size() == b.size() && a < b;
        });
        dic.push_back("");
        vector<vector<int>> dp(s.size() + 1, vector(26, -1));
        /**   dp[i][j]:s中，i位以后字符j出现的位置
         dp[i][j] = i if s[i] = j
         else dp[i][j] = dp[i+1][j]
         */
        for (int i = s.size() - 1; i >= 0; --i)
            for (int j = 0; j < 26; ++j)
                dp[i][j] = s[i] == (j + 'a') ? i : dp[i + 1][j];
        // 判断x是否在s中
        auto check = [&](string &x) {
            int m = x.size(), l = 0, r = 0;
            while (r < m)
                if (!(l = dp[l][x[r++] - 'a'] + 1)) // 跳转 如果碰到-1 则不存在下一个字符，返回false
                    return false;
            return r == m;
        };
        return *find_if(begin(dic), end(dic), check);
    }
};

int main() {
    vector<string> dictionary{"ale", "applv", "monkey", "plea", "appld"};
    Solution solution;
    cout << solution.findLongestWord("abpcplea", dictionary) << endl;
    return 0;
}
